To convolutionally encode a digital data stream in the manner taught by the prior art, n code words of length L (called the constraint length) are employed as a mask. For each mask, the bits of the data stream that appear through the mask are Exclusive OR'd to obtain one parity bit for each mask from the L length of data bits, a total of n parity bits. The bit stream is then moved by k bit position with respect to the mask, and the process is repeated. This results in the generation of another set of n parity bits which includes information from the new L data bits.
If two different code words are used as masks, then two bits of parity information result for every data bit. The ratio of the number of original data bits to the number of replacement parity bits is called the coding rate. Thus, where one data bit is replaced by two parity bits, the coding rate is one half.
As will be understood, Exclusive-OR or modulo 2 sum logical operations are vital to the functioning of convolutional encoders and decoders. Furthermore, it is vital in parity encoding a data stream, that the encoded sequence of parity bits uniquely represents a sequence of data bits. In U.S. Pat. No. 5,077,743 to Bitzer et al., a system is described for decoding a convolutionally encoded data stream that has been encoded at a one half rate. The disclosure of the Bitzer patent is incorporated herein by reference. Bitzer et al. determined that for a constraint length L, code words could be chosen such that a data word of length D would have a unique relationship to a series of parity bits where the following equation was satisfied: EQU D=2(L-1)
Thus, where the length L of a code word is three bits, a convolutional encoding technique can generate two pair of parity bits uniquely related to a four bit data word. As shown by Bitzer et al., for each of sixteen values of 4 bits of data (i.e., 0000-1111), a unique 4 bit parity relationship exists. It can thus be understood that identical mathematical operations may be carried out with respect to corresponding parity and data bit groups, while still maintaining the unique one to one relationship.
It was also shown that the 2.sup.2(L-1) unique relationships between parity and data could be reduced to 2(L`1) relationships, from which the remaining ones could be derived through Exclusive OR functions. Given these unique relationships and an uncorrupted run of parity bits, a decoder could readily reconstruct the data bits from which the parity bits had been originally derived. In FIG. 1, an example is shown of how a sequence of uncorrupted parity bits can be decoded, independent of the data that gave rise to the parity bits. A run of data bits, shown on the top line of FIG. 1 is converted to a run of parity bits P1P2, utilizing a half rate convolutional encoding circuit. It will be noted, that all parity bits are uncorrupted and for half rate encoding two parity bits are generated for each data bit, so that as each data bit moves out of an encoding shift register, two parity bits are transmitted. At the receiving end of a communication link, each time two parity bits are received, a single data bit has been cycled through the encoding shift register. At time TO, two parity pairs, 10 00 are in the decoding register. At time T1, an additional parity pair is received and shifted into the decoding register, etc. On the right side of FIG. 1, each parity pair has been converted to its corresponding data bit sequence, using a conversion table that includes the unique data/parity relations.
By examining the aligned vertical columns of data bits, an important relationship was discerned. In specific, when uncorrupted parity bit pairs were received, the columns of overlapping, derived data expressions were identical. Thus, as each column of data bits was examined, completely identical bits were resident therein. This relationship existed no matter what the data was and thus was totally independent of the data. Thus, if two successive overlapping columns of data bits were Exclusive OR'd together, the result was always zero. Only when there was a parity error, was the zero Exclusive OR relationship not true.
When parity errors occurred in the received parity stream, Bitzer et al. found that the Exclusive OR relationship between overlapping bits in each column of succeeding data bit groups was either zero or a fixed number (N), which number N was dependent only on the code words used to encode the data stream. Thus, as the parity bit stream slid by, two bits at a time, the Exclusive OR differences between successive columnar sets of overlapping data bits produced unique patterns of zeros or ones for any single corrupted parity bit. Also, for any combination of corrupted parity bits, the Exclusive OR operation yielded a unique pattern of zeros and ones, which pattern was the reverse of the code word used to generate the accompanying parity bit position. That unique pattern was thus used to address a correction table that produced bits used to correct the corrupted parity.
Those skilled in the art will realize that the relationships set out in the Bitzer et al. patent established the basis for decoding half rate convolutionally encoded parity streams. That encoding technique was directly dependent upon unique 2(L-1) bit parity to data (and vice versa) relationships. However, for other coding rates, it was then not known how to establish the required unique parity to data relationship to match an encoding rate of other than one half and a chosen constraint length.
Accordingly, it is an object of the present invention to provide a convolutional encoding/decoding method and apparatus for encoding rates other than one half.
It is a further object of this invention to provide a convolutional decoding method and apparatus which exhibits improved decoding capability.
It is another object of this invention to provide a convolutional decoding method and apparatus which is capable of decoding actions in the presence of parity errors that give rise to ambiguous correction results.
It is still another object of this invention to provide a convolutional decoding method and apparatus wherein error correction is enabled by tables that store correction values, the tables enabling reconstruction of lost groups of data.